package com.kenliang.algorithm.sort;

import com.kenliang.algorithm.dateStructure.HeapStructure;

/**
 * @author KenLiang
 * @description: 堆排序，
 * 使用堆结构poll依次取出最小值实现
 *
 * 时间复杂度O(N*logN) 空间复杂度O(1)
 * @date Created in 14:55 2021/1/2.
 */
public class HeapSort implements ISort {
    @Override
    public int[] sort(int[] in) {
        if(in==null || in.length<2){
            return in;
        }
        //组成大根堆
        for(int i=0;i<in.length;i++){
            this.heapInsert(in,i);
        }

        //交换heap中最后一个元素和堆顶元素，然后减少heapSize,heap中排除最后一个元素（最大值），然后heapify,直到heapSize为0
        int heapSize = in.length;
        this.swap(in,0,--heapSize);
        while(heapSize > 0){
            this.heapify(in,0,heapSize);
            this.swap(in,0,--heapSize);
        }
        return in;
    }

    //以下两个方法为大根堆方法

    private void heapInsert(int[] in, int index) {
        int parentIndex = (index - 1) / 2;
        //父>自己
        while (in[parentIndex] < in[index]) {
            this.swap(in, index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    private void heapify(int[] in, int index, int heapSize) {
        int leftChildIndex = index * 2 + 1;
        while (leftChildIndex < heapSize) {
            int rightChildIndex = leftChildIndex + 1;
            int largestIndex = rightChildIndex < heapSize && in[rightChildIndex] > in[leftChildIndex] ? rightChildIndex : leftChildIndex;
            largestIndex = in[index] > in[largestIndex] ? index : largestIndex;
            if (largestIndex == index) {
                break;
            }
            this.swap(in, index, largestIndex);
            index = largestIndex;
            leftChildIndex = index * 2 + 1;
        }

    }
}
